// 动态规划 - 核心 5 步：
// 1. 确定状态表示 - 根据 题目要求，经验(以 i,j 位置为结尾/开始......)，发现重复子问题 确定状态表示
// 2. 推导状态转移方程: dp[i] = ?
//    用 之前的状态 或者 之后的状态 推导当前的状态（根据最近一步划分问题）
// 3. 初始化：保证填表时不越界，结合多开数组的技巧
// 4. 确定填表顺序：填写当前状态值的时候，所需状态的值已经计算过了
// 5. 返回值：结合题目要求 + 状态表示

// 技巧：
// 01 背包问题：使用滚动数组进行优化，删除横坐标，从右往左填表
// 完全背包问题：使用滚动数组进行优化，删除横坐标，从左往右填表
// 似包非包问题：从重复子问题的角度入手分析 dp

// 例题 12:
// 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
//
//        示例 1：
//
//
//        输入：n = 3
//        输出：5
//        示例 2：
//
//        输入：n = 1
//        输出：1
//
//
//        提示：
//
//        1 <= n <= 19

// 解题思路:
// dp[i] 表示 i 个数的二叉搜索树的数量
// 初始化：dp[0] = 1
// 根据根节点的位置分类讨论，设根节点的位置为 j (1 <= j <= i)
// dp[i] += dp[j - 1] * dp[i - j]

public class NumTrees {
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++){
            for(int j = 1; j <= i; j++){
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
}
